package study.datastructure.graph;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-05 23:25
 */

import java.util.LinkedList;

/**
 2024/6/5,
 */

//邻接表实现图
public class Graph {
    //顶点数量
    private Integer numVertices;

    //邻接表存储
    private LinkedList<Integer>[] adjacencyList;

    public Graph(Integer numVertices){
        this.numVertices = numVertices;
        adjacencyList=new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjacencyList[i]=new LinkedList<Integer>();
        }
    }

    //添加边 无向图
    public void addEdge(int src,int dest){
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src); //无向图两边都添加
        System.out.println("添加边成功 ("+src+","+dest+")");
    }

    // 打印图
    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("顶点 " + i + " 连接到: ");
            for (Integer vertex : adjacencyList[i]) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    //深度优先搜索
    public void depthFirstSearch(Integer vertex){ //起始顶点
        boolean[] visited = new boolean[numVertices];
        depthFirstSearchUtil(vertex,visited);

    }

    private void depthFirstSearchUtil(Integer vertex, boolean[] visited) {
        visited[vertex] =true;
        System.out.println("访问节点"+vertex);

        for (Integer neighbor : adjacencyList[vertex]) { //邻接点一个个遍历
            if (!visited[neighbor]){
                depthFirstSearchUtil(neighbor,visited);
            }
        }
    }

    //广度优先遍历
    // 广度优先搜索（BFS）
    public void breadthFirstSearch(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int neighbor : adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    // 测试图
        public static void main(String[] args) {
            Graph graph = new Graph(5);

            graph.addEdge(0, 1);
            graph.addEdge(0, 4);
            graph.addEdge(1, 2);
            graph.addEdge(1, 3);
            graph.addEdge(1, 4);
            graph.addEdge(2, 3);
            graph.addEdge(3, 4);

            graph.printGraph();

            System.out.println("深度优先搜索 (DFS) 起始于顶点 0:");
            graph.depthFirstSearch(0);

            System.out.println("\n广度优先搜索 (BFS) 起始于顶点 0:");
            graph.breadthFirstSearch(0);
        }

}
